package a07_二叉树;

/**
 * <p>
 * a30_删除二叉搜索树中的节点复习1
 * </p>
 *
 * @author flyduck
 * @since 2024/12/26
 */
public class a30_删除二叉搜索树中的节点复习1 {

    public TreeNode deleteNode(TreeNode currentNode, int key) {
        if (currentNode == null) {//没找到
            return null;
        }else if(currentNode.val == key){//找到节点了，删除节点
           if(currentNode.left == null && currentNode.right == null){
               return null;
           }else if(currentNode.left != null && currentNode.right == null){
               return currentNode.left;
           }else if(currentNode.left == null && currentNode.right != null){
               return currentNode.right;
           }else {
               TreeNode mostLeftNode = currentNode.right;
               while (mostLeftNode.left != null) {
                   mostLeftNode = mostLeftNode.left;
               }

               mostLeftNode.left = currentNode.left;
               return currentNode.right;
           }
        }

        if (key > currentNode.val) {
            currentNode.right = deleteNode(currentNode.right, key);
        }else {
            currentNode.left = deleteNode(currentNode.left, key);
        }
        return currentNode;
    }
}
